package com.chj.zhongji.class10;

public class Code03_MinPatches {

	public static int minPatches(int[] arr, int K) {
		int patches = 0; // 缺多少个数字
		long range = 0; // 已经完成了1 ~ range的目标
		for (int i = 0; i != arr.length; i++) {
			// 1~range
			// arr[i]
			// 1~arr[i]-1
			while (arr[i] > range + 1) { // arr[i] 1 ~ arr[i]-1
				range += range + 1; // range + 1 是缺的数字
				patches++;
				if (range >= K) {
					return patches;
				}
			}
			range += arr[i];
			if (range >= K) {
				return patches;
			}
		}
		while (K >= range + 1) {
			range += range + 1;
			patches++;
		}
		return patches;
	}

	public static void main(String[] args) {
//		{
//			int[] test = { 1, 2, 31, 33 };
//			int n = 2147483647;
//			System.out.println(minPatches(test, n));
//		}
//
//		{
//			int[] test = { 1, 2, 3, 7 };
//			int n = 15;
//			System.out.println(minPatches(test, n));
//		}

		{
			int[] test = { 1, 5, 7 };
			int n = 15;
			System.out.println(minPatches(test, n));
		}
	}

}
